package classes.graphicalEngine
{
    
    import flash.geom.Point;
    
    
    /**
    * Implémentation de la recherche d'un plus court chemin entre deux points
    * dans une matrice, en utilisant l'algorithme "a*" ou "a star"
    */
    public class Astar {
        
        /** Les noeuds à visiter **/
        private var aVoir:Array;
        
        /** Les noeuds déjà visités **/
        private var dejaVus:Array;
        
        /** La matrice qui sert de cadre de recherche **/
        private var matrice:Array;
        
        /** Le point de départ **/
        private var depart:Point;
        
        /** Le point d'arrivée **/
        private var arrivee:Point;
        
        /** Peut-on utiliser les diagonales pour se déplacer ? **/
        private var deplacementDiagonal:Boolean;


        
        /**
        * Constructeur
        */
        public function Astare(dep:Point, arr:Point, mat:Array, diag:Boolean = false):Array {
            // on initialise tous les attributs
            this.aVoir = new Array();
            this.dejaVus = new Array();
            this.depart = dep;
            this.arrivee = arr;
            this.matrice = mat;
            this.deplacementDiagonal = diag;
            
            // on crée le noeud de départ et on l'ajoute à la liste des "déjà vus"
            var noeudDep:Noeud = new Noeud(this.depart, null, 9999, 0, 0);
            this.dejaVus.push(noeudDep);
            
            // on ajoute tous les adjacents à la liste des "à voir"
            ajouterAdjacents(noeudDep);
            
            // on déclare un noeud courant
            var noeudCourant:Noeud = noeudDep;
        
            // on boucle tant que le point d'arrivée n'est pas atteint et qu'un chemin est possible
            while (this.aVoir.length > 0 && !noeudCourant.position.equals(this.arrivee)) {
                // on lance un tri (sur f) sur le tableau des noeuds à visiter de sorte 
                // d'avoir toujours le meilleur à portée de main 
                this.aVoir.sort(Noeud.trieur, Array.DESCENDING);
                // on récupère donc le meilleur f (celui du fond donc) et on l'ajoute aux "déjà vus"
                noeudCourant = Noeud(aVoir.pop());
                this.dejaVus.push(noeudCourant);
                // on rajoute les adjacents au noeud courant aux "à voir"
                ajouterAdjacents(noeudCourant);
            }
            // on retourne le chemin approchant trouvé (pas forcément jusqu'au point d'arrivée...)
            return getChemin(noeudCourant);
        }
        
        
        
        /**
        * Renvoie le chemin déterminé par l'algorithme de plus court chemin
        * (grâce à l'attribut "parent" conservé par chaque noeud)
        */ 
        public function getChemin(noeud:Noeud):Array {
            var chemin:Array = new Array();
            // on remonte dans la hiérarchie tant que le noeud courant a un parent
            while (noeud.parent != null) {
                chemin.push(noeud.position);
                noeud = trouverNoeud(noeud.parent, this.dejaVus);
            }
            return chemin;
        }
        
        
        
        /**
        * Ajouter les noeuds adjacents à la liste des "à voir" 
        */
        public function ajouterAdjacents(noeud:Noeud):void {
            // on ne cherche que les adjacents
            for (var i:int = -1; i <= 1; i++) {
                for (var j:int = -1; j <= 1; j++) {
                    
                    // on ignore le cas du milieu [0,0] (bien sûr !)
                    if (i == 0 && j == 0) continue;
                    
                    // on vérifie que l'on se trouve bien dans la matrice
                    if (noeud.position.y + j < 0 || noeud.position.x + i < 0) continue;
                    else if (noeud.position.y + j >= this.matrice.length || noeud.position.x + i >= this.matrice[noeud.position.y].length) continue; 
                    
                    // si le déplacement en diagonal n'est pas autorisé on le gère
                    // si la somme des indices i et j est supérieure à 1 on est certain que ce soit une diagonale 
                    if (!this.deplacementDiagonal && Math.abs(i) + Math.abs(j) > 1) {
                        if (matrice[noeud.position.y + j][noeud.position.x] == 1) continue;
                        if (matrice[noeud.position.y][noeud.position.x + i] == 1) continue;
                    }
                    
                    // on revérifie que le noeud soit bon (A REVOIR MAYBE...)
                    if (matrice[noeud.position.y + j][noeud.position.x + i] == 0) {
                        // on crée un nouveau noeud en lui calculant G, H et F
                        var pos:Point = new Point(noeud.position.x + i, noeud.position.y + j);
                        var g:int = calculerG(pos, noeud);
                        var h:int = calculerH(pos);
                        var f:int = g + h;
                        var nouveauNoeud:Noeud = new Noeud(pos, noeud.position, f, g, h); 
                        
                        // on cherche le noeud dans la liste des "à voir"
                        var ancienNoeud:Noeud = trouverNoeud(nouveauNoeud.position, aVoir);
                        // si il n'y est pas déjà (dans les "à voir")
                        if (ancienNoeud == null) {
                            // et si il n'est pas dans la liste des "déjà vus", on l'ajoute aux "à voir"
                            if (trouverNoeud(nouveauNoeud.position, dejaVus) == null) {
                                aVoir.push(nouveauNoeud);
                            }
                        }
                        // sinon il y est déjà, on vérifie que ce soit bien le meilleur chemin jusqu'ici
                        else if (g < ancienNoeud.g) {
                            // si c'est le cas, on remplace par le nouveau
                            trouverNoeud(pos, aVoir, nouveauNoeud);
                        }
                    }
                }
            }
        }
        
        
        
        /**
        * Permet de trouver un noeud par sa position dans un tableau de noeuds
        * et accessoirement si l'on précise le paramètre noeud, il sera remplacé par celui-ci
        */
        private function trouverNoeud(pos:Point, tab:Array, noeud:Noeud = null):Noeud {
            // on parcourt le tableau à la recherche du noeud perdu
            for (var i:int = 0; i < tab.length; i++) {
                // si c'est le bon, on le retourne
                if (pos.equals(Noeud(tab[i]).position)) {
                    if (noeud) {
                        tab[i] = noeud;
                    } 
                    return Noeud(tab[i]);
                }
            }
            return null;
        }
        
        
        
        /**
        * Calcul de G, i.e. le coût du trajet jusqu'ici (en considérant le chemin déjà trouvé)
        */
        private function calculerG(pos:Point, noeud:Noeud):int {
            var resultat:int;
            var dif:int = Math.abs(pos.x - noeud.position.x) + Math.abs(pos.y - noeud.position.y);
            if (dif == 1) resultat = 10;
            if (dif == 2) resultat = 14;            
            return resultat + noeud.g;
        }
        
        
        
        /**
        * Heuristique de calcul du plus court chemin : ici on utilise la distance 
        * à vol d'oiseau, chose aisée dans une matrice
        */
        private function calculerH(pos:Point):int {
            return (Math.abs(pos.x - this.arrivee.x) + Math.abs(pos.y - this.arrivee.y)) * 10;
        }

    }
}